package com.gitee.ywj1352.算法.week02;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class 二叉树的深度 {
    public static int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int r = maxDepth(root.right);
        int l = maxDepth(root.left);
        return Math.max(r, l) + 1;
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(7);
        TreeNode t8 = new TreeNode(8);
        t5.left = t3;
        t5.right = t8;
        t3.left = t2;
        t3.right = t4;
        t2.left = t1;
        t8.left = t6;
        t8.right = t7;

        System.out.println(maxDepth(t5));

    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayDeque<TreeNode> deque = new ArrayDeque<TreeNode>();

        deque.addFirst(root);

        List<List<Integer>> res=  new ArrayList<>();
        boolean a = false;
        while(!deque.isEmpty()){
            int size = deque.size();
            ArrayList<Integer> ints = new ArrayList<Integer>();
            for(int i = 0; i< size; i++){
                TreeNode curr = a ? deque.removeFirst(): deque.removeLast();
                ints.add(curr.val);
                if(curr.left !=null)
                    deque.addFirst(curr.left);
                if(curr.right !=null)
                    deque.addFirst(curr.right);
            }
            res.add(ints);
            a = !a;
        }

        return res;
    }
}
